package Sort;


/**
 * 排序(3)
 * 希尔排序
 * 思想:使数组中任意间隔为h的元素都是有序.(也称h有序数组)
 * 基于插入排序，但效率更高
 * 插入排序只能交换相邻元素，若最小元素在尽头，需交换(数组长度-1)次，效率低
 * 原理:交换不相邻的元素以对数组的局部进行排序，最终插入排序将局部有序的数组排序。
 */
public class ShellSort extends Template {


//插入排序 交换次数71
//    int N = a.length;
//        for (int i = 1; i < N; i++) {
//        for (int j = i; j > 0 && less(a[j], a[j - 1]); j--) {
//            exch(a, j, j - 1);
//        }
//    }
    static int changeCount = 0;


    //希尔排序 交换次数25
    //升序
    public static void sort(Comparable[] a) {
        int N = a.length;
        int h = 1;
        while (h < N / 3) h = 3 * h + 1;//1,4,13,40,121
        //System.out.println("h=" + h);//4

        while (h >= 1) {
            //**********插入排序
            for (int i = h; i < N; i++) {
                for (int j = i; j >= h && less(a[j], a[j - h]); j -= h) {
                    exch(a, j, j - h);
                    //记录交换次数
                    changeCount++;
                }
            }
            //**********插入排序
            h = h - 3;
            //System.out.println("h=" + h);
        }

        //System.out.println("交换次数" + changeCount);

    }


//    //无注释
//    public static void sort(Comparable[] a) {
//        int N = a.length;
//        int h = 1;
//        while (h < N / 3) h = 3 * h + 1;
//        while (h >= 1) {
//            for (int i = h; i < N; i++) {
//                for (int j = i; j >= h && less(a[j], a[j - h]); j -= h) {
//                    exch(a, j, j - h);
//                }
//            }
//            h = h - 3;
//        }
//    }


    public static void main(String[] args) {
        //String[] a = {"c", "s", "d", "n", "x", "i", "n", "g", "w", "e", "i", "s", "h", "e", "l", "l", "s", "o", "r", "t"};
        Comparable[] a=Template.getData(20);
        System.out.println("希尔排序前");

        show(a);
        sort(a);

        assert isSorted(a);
        System.out.println("希尔排序后");
        show(a);
    }

}
